package lc_1483_树节点的第_K_个祖先;

import java.util.Arrays;

public class TreeAncestor {

	int[][] dp;

	public TreeAncestor(int n, int[] parent) {
		int m = 17;
		dp = new int[n][m];
		for (int i = 0; i < n; i++) {
			Arrays.fill(dp[i], -1);
			dp[i][0] = parent[i];
		}
		for (int j = 1; j < m; j++) {
			for (int i = 1; i < n; i++) {
				if (dp[i][j - 1] != -1)
					dp[i][j] = dp[dp[i][j - 1]][j - 1];
			}
		}
	}

	public int getKthAncestor(int node, int k) {
		if (node == -1 || k == 0) {
			return node;
		}
		int lb = k & -k;
		return getKthAncestor(dp[node][Integer.numberOfTrailingZeros(lb)], k - lb);
	}

	public int getKthAncestor3(int node, int k) {
		if (node == -1 || k == 0) {
			return node;
		}
		for (int i = 0; i < 17 && node != -1; i++) {
			if (((k >> i) & 1) == 1) {
				node = dp[node][i];
			}
		}
		return node;
	}

	public int getKthAncestor2(int node, int k) {
		if (node == -1 || k == 0) {
			return node;
		}
		int lb = k & -k;
		return getKthAncestor(dp[node][31 - Integer.numberOfLeadingZeros(lb)], k - lb);
	}

//	int a = (int) (Math.log(k) / Math.log(2));
//	k -= (int) Math.pow(2, a);
	public static void main(String[] args) {
		int a = 10086;
		System.out.println(Integer.toBinaryString(a));
		System.out.println(Integer.toBinaryString(a).length());
		System.out.println(Integer.numberOfLeadingZeros(a));
		System.out.println(32 - Integer.numberOfLeadingZeros(a));

//		while (a > 0) {
//			int lb = a & -a;
//			System.out.println(lb + " " + Integer.toBinaryString(lb).length());
//			a -= lb;
//		}
	}

}
